package map.myHashMap;

/**
 * 基于拉链法实现的哈希表
 */
public class HashMapByLink {
    //实际存储每个节点
    private class Node{
        int key;
        int val;
        Node next;
        public Node(int key,int val,Node next){
            this.key = key;
            this.val = val;
            this.next = next;
        }
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    //实际存储的元素个数
    private int size;
    //取模数
    private int M;
    //默认哈希表的长度
    private static final int DEFAULT_CAPACITY = 16;
    //默认的负载因子
    private static final double LOAD_FACTOR = 0.75;
    //实际存储Node节点的数组
    private Node[] table;
    public HashMapByLink(){
        this(DEFAULT_CAPACITY);
    }
    public HashMapByLink(int initCap){
        this.table = new Node[initCap];
        this.M = initCap;
    }
    //对key取模
    private int hash(int key){
        return (key & 0x7fffffff) % this.M;
    }
    /**
     * 向哈希表中添加一个键值对
     * @param key
     * @param value
     * @return 若没有重复元素，返回value，若key已经存在，更新为新的value,返回之前的value
     */
    public int put(int key,int value){
        //1.求key的哈希值
        int index = hash(key);
        //2.判断当前哈希表中是否已经存在了这个key，若存在，更新为新的val值，返回旧的value
        for (Node x = table[index]; x != null; x = x.next){
            if(x.key == key){
                //此时链表中已经包含了key，更新为新的value，返回旧的value
                int oldVal = x.val;
                x.val = value;
                return oldVal;
            }
        }
        //3.此时key不存在，新建一个节点，头插入相应的链表
        Node newNode = new Node(key,value,table[index]);
        //此时新节点已经指向了原先的头节点,更新原先头节点的指向
        table[index] = newNode;
        size ++;
        //4.扩容
        if(size >= LOAD_FACTOR * table.length){
            resize();
        }
        return value;

    }

    /**
     * 扩容操作，默认将哈希表长度扩大二倍
     */
    private void resize() {
        Node[] newTable = new Node[table.length << 1];
        this.M = newTable.length;
        //遍历哈希表更新节点存储位置
        for (int i = 0; i < table.length; i++) {
            Node next = null;
            for(Node cur = table[i]; cur != null;cur = next){
                next = cur.next;
                int newIndex = hash(cur.key);
                //头插入新的哈希表
                cur.next = newTable[newIndex];
                newTable[newIndex] = cur;
            }
        }
        this.table = newTable;
    }

    /**
     * 删除哈希表中指定的键值对
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key,int value){
        int index = hash(key);
        if(table[index].key == key){
            //此时头节点就是待删除的节点
            if(table[index].val == value){
                table[index] = table[index].next;
                size --;
                return true;
            }
        }
        //头节点不是待删除的节点
        Node prev = table[index];
        while (prev != null){
            if (prev.next.key == key){
                if (prev.next.val == value){
                    prev.next = prev.next.next;
                    size --;
                    return true;
                }
            }
            prev = prev.next;
        }
        return false;
    }

    public boolean containsKey(int key){
        return false;
    }
    public boolean containsValue(int value){
        return false;
    }

    /**
     * 根据key值取得相应的value值
     * @param key
     * @return
     */
    public int get(int key){
        //求出当前key对应的索引
        int index = hash(key);
        //遍历index对应的链表，返回key对应的索引
        for (Node x = table[index]; x != null; x = x.next){
            if (x.key == key){
                return x.val;
            }
        }
        //此时循环走完还没找到，返回-1
        return -1;
    }
}
